/*
 * @lc app=leetcode.cn id=130 lang=cpp
 * @lcpr version=30204
 *
 * [130] 被围绕的区域
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();
        vector<pair<int,int>> directions = {
            {0, -1},    // 上
            {0, 1},     // 下
            {-1, 0},    // 左
            {1, 0}      // 右
        };

        auto dfs = [&](this auto&& dfs, int x, int y) {
            if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') {
                return;
            }

            board[x][y] = 'T'; // 标记为临时字符
            for(auto [dx, dy] : directions) {
                int nx = x + dx;
                int ny = y + dy;
                dfs(nx, ny);
            }
        };

        // 遍历四条边，启动 DFS
        for (int i = 0; i < m; ++i) {
            dfs(i, 0);       // 左边
            dfs(i, n - 1);   // 右边
        }
        for (int j = 1; j < n - 1; ++j) { // 上下边（去掉四角，避免重复）
            dfs(0, j);
            dfs(m - 1, j);
        }
        
        // 第二步：转换未被标记的 O（被包围的）为 X，并还原标记的 T 为 O
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X'; // 被包围的 O
                if (board[i][j] == 'T') board[i][j] = 'O'; // 还原边缘连通的 O
            }
        }
    }
};
// @lc code=end



/*
// @lcpr case=start
// [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]\n
// @lcpr case=end

// @lcpr case=start
// [['X']]\n
// @lcpr case=end

 */

